package Sort;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * @Author Fizz Pu
 * @Date 2021/3/12 下午5:57
 * @Version 1.0
 * 失之毫厘，缪之千里！8
 *
 *   ,
 */

//插入排序
// 时间复杂度: 最坏O(n**2) 最好O(n)  稳定排序
// 适用场景: 基本有序的情况

// 0 2 1 3 3 9
public class InsertSort implements SortAlgrithom {

    @Override
    public void sort(int[] arr) {
        if(arr == null){
            throw new IllegalArgumentException();
        }

        int len = arr.length;
        for(int i = 1; i < len; i++){
            int temp = arr[i];
            int j = i - 1;
            for(; j >= 0 && arr[j] > temp; j--){
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}
